#include "KNode.h"
#include "KDTree.h"
#include <math.h>
#include "MREAgent.h"

                                     // newmatap.h will get include.h


//using namespace NEWMAT; 

//#define		DEBUG_PRINT

double* KRect::widths; 




KRect::KRect()
{
	size = 0; 
	size_normalized = 0; 
	dim = 0; 
	mins = maxs = 0; 
}


KRect::KRect(int _dim, double_range_t* r)
{
	setBox(_dim, r); 
}

void KRect::setBox(int _dim, double* _mins, double* _maxs)
{
	dim = _dim; 
	mins = new double[dim]; 
	maxs = new double[dim]; 
	memcpy(mins, _mins, dim*sizeof(double)); 
	memcpy(maxs, _maxs, dim*sizeof(double)); 
	_computeSize(); 
}
void KRect::setBox(int _dim, double_range_t* r)
{
	dim = _dim; 
	mins = new double[dim]; 
	maxs = new double[dim]; 
//	memcpy(mins, _mins, dim*sizeof(double)); 
//	memcpy(maxs, _maxs, dim*sizeof(double)); 
	for(int i=0; i< dim; i++)
	{
		mins[i] = r[i].min; 
		maxs[i] = r[i].max; 
	}

	_computeSize(); 
}


void KRect::_computeSize()
{
	size = 0 ; 
	size_normalized = 0; 

	for(int i=0; i< dim; i++)
	{
		double nwidth = (maxs[i] - mins[i]) / widths[i] ; 
		if ( maxs[i] - mins[i] > size)
			size = maxs[i] - mins[i]; 
		if (nwidth > size_normalized)
			size_normalized = nwidth; 
	}

}

KRect::~KRect()
{
	reset(); 
}

void KRect::reset()
{
	if (isValid())
	{
		delete mins; 
		delete maxs; 
		dim = 0; 
		size = 0; 
		size_normalized = 0; 
	}
}


bool KRect::isValid()
{
	return dim != 0; 
}



void KRect::split(KRect* lhs, KRect* rhs, int dimIndex, double splitVal)
{
#ifdef	DEBUG_PRINT
	printf("splitting in direction %d\n", dimIndex); 
#endif


	lhs->reset(); 
	rhs->reset(); 

	lhs->setBox(dim, mins, maxs); 
	rhs->setBox(dim, mins, maxs); 
	lhs->maxs[dimIndex] = splitVal ; 
	rhs->mins[dimIndex] = lhs->maxs[dimIndex]; 

	lhs->_computeSize(); 
	rhs->_computeSize(); 

}


void KNode::init()
{
	psize = 0; 
	parent = 0; 
	m_tree = 0; 
	box = 0; 
	left = right = 0; 
	 

}

KNode::KNode(KDTree* t,KNode* p,  KRect* r)
{
	id = t->totalNodes; 

	init(); 

	m_tree = t; 
	m_tree->totalNodes++; 

	parent = p; 
	box = r; 
	splitDirection = -1; 
	splitValue = 0; 
	solver = 0;			//we create solver when we have enough points

}



KNode::KNode(void)
{
	id = -1; //no access to its tree
	init(); 
}

KNode::~KNode(void)
{
	if (!isLeaf())
	{
		delete left; 
		delete right; 
		if (box)
			delete box; 

	}else
	{
		if (solver)
		{
			if (solver->size != psize)
			{
				printf("not possible: my size %d, solver size %d\n", psize, solver->size ); 
				throw(0); 
			}

			delete solver; 
		}

		if (box)
			delete box; 
	}
}

void KNode::examineNode()
{
	//why do we want to examine a non-leaf node? 
	if (!isLeaf())
		return; 


	if (psize > m_tree->maxNumberOfSamples && box->size_normalized > m_tree->knownMaxLength)
		split(); 
	else
	{
		if (m_tree->splitCriterion == KDTree::SPLIT_USE_MAX_ALLOWED_ERROR  && psize >= m_tree->knownMinPoints) 
		{
			if (!solver)
				createLocalSolver(); 

			double err = solver->addData(points); 
			if (err > m_tree->maxAllowedError ) 
				split(); 
		}
		else if (m_tree->splitCriterion == KDTree::SPLIT_USE_MAX_SAMPLES ) 
		{
			if (psize > 5*m_tree->maxNumberOfSamples && box->size_normalized < m_tree->knownMaxLength && box->size_normalized > m_tree->knownMaxLength / 5)
				split(); 
			else{
				if (!solver)
					createLocalSolver(); 

				solver->addData(points); 
			}
		}


	}

/*
	if (box->size_normalized > m_tree->knownMaxLength)//this cell will never be a known one as its too big
	{
		if (psize > (unsigned int) m_tree->knownMinPoints )//if we have enough points, lets split it
			split(); 	
	}else	//its small enough to be a known state
	{
		if (psize > (unsigned int) m_tree->knownMinPoints ) //has enough points to be  known 
		{
			if (m_tree->splitCriterion == KDTree::SPLIT_USE_MAX_ALLOWED_ERROR ) 
			{
				if (!solver)
					createLocalSolver(); 

				double err = solver->addData(points); 
				if (err > m_tree->maxAllowedError ) 
					split(); 
				else
					isKnown = true; 
			}
			else if (m_tree->splitCriterion == KDTree::SPLIT_USE_MAX_SAMPLES ) 
			{
				if (psize > m_tree->maxNumberOfSamples && box->size_normalized > m_tree->knownMaxLength / 10) //warning:
					split(); 
				else
				{
					isKnown = true; 
					if (!solver)
						createLocalSolver(); 
					solver->addData(points); 
				}
			}


		}
	}
*/
}

double KNode::getKnownness()
{
/*	//fixed resolution 
	if (box->size_normalized > m_tree->knownMaxLength)
		return 0; 

	if (psize >= m_tree->knownMinPoints )
		return 1.0; 
	else
		return 0; 
*/


	//variable resolution
	double smallness = 0; 
	double t = m_tree->knownMaxLength ; 
	double x = box->size_normalized; 
	if (x <= t)	
		smallness = 1; 
	else if (x <= m_tree->eta)		//the first line  
		smallness = (x-t)*(m_tree->eta-1)/ (m_tree->eta-t)*(1-t)  +1 ; 
	else 
		smallness = (x-1)*(m_tree->eta - t) / (m_tree->eta -1)*(1-t); 

	if (psize >= m_tree->knownMinPoints)
		return smallness;  
	else	//do not return 0
	{
		return psize / (double) m_tree->knownMinPoints * smallness; 
	}

}


double KNode::getPublicKnownness(Observation st)
{
	if (!isLeaf())	//delegate to appropriate child
	{
		if(st[splitDirection] > splitValue)
			return right->getPublicKnownness(st); 
		else
			return left->getPublicKnownness(st); 
	}

	//we're a leaf
	return getKnownness(); 



}

int KNode::getNumberOfNodes()
{
	int result =1;
	if (left)
		result += left->getNumberOfNodes();

	if (right)
		result += right->getNumberOfNodes();

	return result; 

}


void KNode::clearData()
{
	points.clear(); 
	psize = 0; 

	if (!isLeaf())
	{
		left->clearData(); 
		right->clearData(); 
		return; 
	}


	//this is a leaf
	if (solver)
	{
		delete solver; 
		solver = 0; 
	}


}

void KNode::createLocalSolver()
	{
		if(solver)
			delete solver; 

		switch(m_tree->generalizerType)
		{
		case KDTree::GENERALIZER_USE_MEAN: 
			solver = new LocalAverager(this, m_tree->dimension); 
			break;
		case KDTree::GENERALIZER_USE_LINEAR:
			//solver = new LinearSolver(this, m_tree->dimension); 
			break;
		}
	}





void KNode::addPointsToCurrentStructure(list<KData>& l)
{
	if (!isLeaf())
	{
		psize += l.size(); 
	list<KData>* l1 = new list<KData>(); 
	list<KData>* l2 = new list<KData>(); 

		splitData(l, *l1, *l2, splitDirection); 

		left->addPointsToCurrentStructure(*l1); 
		delete l1;
		right->addPointsToCurrentStructure(*l2); 
		delete l2; 

		return;
	}


	//this is a leaf
	addPoints(l); 

}


void KNode::addPoint(KData&  pt)
{

	psize++; 

#ifdef	DEBUG_PRINT
	printf("add point to node %d\n", id); 
#endif

	points.push_back(pt);	//add data to the node
	if (! isLeaf())
	{
		//find the child that should this go into 
		if (pt.first[splitDirection] <= splitValue)
			left->addPoint(pt); 
		else
			right->addPoint(pt); 
	}
	else	//this node is a leaf node
	{
		examineNode(); 

	}
}

double computeMean(list<KData>& l)
{
	if (l.empty())
		return 0; 

	double result = 0; 

	for(list<KData>::iterator it = l.begin(); it != l.end(); it++)
		result += (*it).second; 

	return result /= l.size(); 
}



int KNode::getSplitDimension()
{
//	return  rand() / (RAND_MAX / m_tree->dimension);

/*
	int minIndex = 0; 
	double minError = 9999; 

	list<KData> lleft; 
	list<KData> lright; 
	for(int i=0; i< box->dim ; i++)
	{
		splitData(points, lleft, lright, i); 
		
		double lerror = -1; 
		double rerror = -1; 
		if (lleft.size() > m_tree->knownMinPoints ) 
		{
			LinearSolver* s = new LinearSolver(box->dim); 
			lerror = s->addData(lleft); 
			delete s; 
		} else
			lerror = - lleft.size(); 

		if (lright.size() > m_tree->knownMinPoints)
		{
			LinearSolver* s = new LinearSolver(box->dim); 
			rerror = s->addData(lright); 
			delete s; 
		}else
			rerror = - lright.size(); 

		if ( rerror < 0 && lerror >= 0 ) 
			rerror = lerror / (-rerror); 
		else if (lerror < 0 && rerror >= 0)
			lerror = rerror / (-lerror); 
		else if (lerror < 0 && rerror < 0 ) 
		{
			if (lerror < rerror ) 
				rerror = lerror = - rerror; 
			else
				rerror = lerror = - lerror; 

		}

		double error = (lerror + rerror)/ 2; 
		
		if (error < minError) 
		{
			minIndex = i; 
			minError = error; 
		}

		printf("exammining %d, minIndex %d, error %lf, minError %lf\n",i, minIndex, error , minError); 


		lleft.clear(); 
		lright.clear(); 

	}

	return minIndex; 
*/

	if (parent)
	{
		return (parent->splitDirection + 1) % MREAgent::dimension ; 
	}
	else
		return 0;


	int maxIndex = 0; 
	double maxDist = 0; 

	list<KData> lleft; 
	list<KData> lright; 
	for(int i=0; i< box->dim ; i++)
	{
		splitData(points, lleft, lright, i); 

		double lmean = computeMean(lleft); 
		double rmean = computeMean(lright); 
		double objective = fabs(lmean-rmean) + box->maxs[i] - box->mins[i]; 
		if ( objective > maxDist)
		{
			maxDist = objective; 
			maxIndex = i; 
		}
	}

	return maxIndex; 

}


//puts each point in l into one of the l1 or l2 according to split condition
void KNode::splitData(list<KData> l, list<KData>& l1, list<KData>& l2, int splitDim)
{

	for(list<KData>::iterator it = l.begin(); it != l.end(); it++)
	{
		Observation x = (*it).first ; 
		double side = drand48(); 
		
		if ( x[splitDim] < splitValue)
			l1.push_back(*it); 
		else if (x[splitDim] > splitValue)
			l2.push_back(*it); 
		else
		{
			l1.push_back(*it); 
/*			if (side > 0.5)
				l1.push_back(*it); 
			else
				l2.push_back(*it); 
*/		}
	}
}


void KNode::split()
{

//	printf("split node %d\twith %d\t\tdata, box size\t%lf\n", id, psize, box->size_normalized ); 
	splitDirection = getSplitDimension();
	list<KData>* l1 = new list<KData>(); 
	list<KData>* l2 = new list<KData>(); 

	//compute a split value: 
	splitValue = (box->maxs[splitDirection]  + box->mins[splitDirection]) / 2.0; 

/*
	const int tries = 5; 
	int rndTmp[tries]; //indices for guessed median
	int lefts[tries]; //how many points are there to the left of each median
	double splitVals[tries]; //the split value for each guessed median
	

	for(int i=0; i< tries; i++)
	{
		rndTmp[i] = intRand(psize-1); 
		lefts[i] = 0; 
	}
	//find split vals
	int cntr = 0; 
	for(list<KData>::iterator it= points.begin(); it != points.end(); it++, cntr++)
	{
		for(int j=0; j< tries; j++)
		{
			if (cntr==rndTmp[j])
				splitVals[j] = (*it).first[splitDirection]; 
		}
	}

	//fill in the lefts
	for(list<KData>::iterator it= points.begin(); it != points.end(); it++)
	{
		double val = (*it).first[splitDirection];
		for(int j=0; j< tries; j++)
		{
			if (val < splitVals[j])
				lefts[j]++;
		}		
	}


	int actualMedian = psize / 2; 
	int bestMedianDist = abs(actualMedian - lefts[0]); 
	int bestMedianInd = 0; 
	for(int j=1; j< tries; j++)
	{
		if ( abs(actualMedian - lefts[j]) < bestMedianDist)
		{
			bestMedianDist = abs(actualMedian - lefts[j]); 
			bestMedianInd = j; 
		}
	}
	
	splitValue = splitVals[bestMedianInd]; 
*/	
//-------------finished computing splitValue



	splitData(points, *l1, *l2, splitDirection); 

	KRect * lbox = new KRect(); 
	KRect* rbox = new KRect(); 

	box->split(lbox, rbox, splitDirection, splitValue); 

	left = new KNode(m_tree, this,  lbox); 
	right = new KNode(m_tree, this, rbox); 

	left->addPoints(*l1);
	delete l1; 
	
	right->addPoints(*l2); 
	delete l2; 

	points.clear();			//we don't keep the points for internal nodes

	if (solver)
		delete solver; 

}


void KNode::addPoints(list<KData>& l)
{

	psize += l.size(); 

#ifdef	DEBUG_PRINT
	printf("add list of points to node %d\n", id); 
#endif


	for(list<KData>::iterator  it= l.begin(); it != l.end(); it++)
		points.push_back(*it); 

	examineNode(); 
}


bool KNode::predict(Observation pt, double& result)
{
	if (!isLeaf())	//delegate to appropriate child
	{
		if(pt[splitDirection] > splitValue)
			return right->predict(pt, result); 
		else
			return left->predict(pt, result); 
	}

	if (getKnownness() ==0)
		return false; 


	result = 	solver->predict(pt);
	return true; 

}                                                                                                                                                                                                                                                                                                                                                                                                                                      


void KNode::createRandomPoints(list<KData>& l,int sampleNumber)
{
	if (!isLeaf())
	{
		left->createRandomPoints(l, sampleNumber); 
		right->createRandomPoints(l, sampleNumber); 
		return; 
	}

	if (getKnownness()==0)
		return; 

	for(int i=0; i< sampleNumber; i++)
	{
		Observation o = new Observation_type[box->dim]; 
		for(int j=0; j< box->dim; j++)
		{
			o[j] = floatRand(box->mins[j] , box->maxs[j]); 
		}

		KData d(o,-1); 
		l.push_back(d); 
	}
}









